; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
; RUN: opt < %s -passes=instcombine -S | FileCheck %s

declare void @use8(i8)
declare void @use32(i32)

; These would crash if we didn't check for a negative shift.

; https://llvm.org/bugs/show_bug.cgi?id=12967

define void @pr12967() {
; CHECK-LABEL: @pr12967(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br label [[LOOP:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    br label [[LOOP]]
;
entry:
  br label %loop

loop:
  %c = phi i32 [ %shl, %loop ], [ undef, %entry ]
  %shr = shl i32 %c, 7
  %shl = lshr i32 %shr, -2
  br label %loop
}

; https://llvm.org/bugs/show_bug.cgi?id=26760

define void @pr26760() {
; CHECK-LABEL: @pr26760(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br label [[LOOP:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    br label [[LOOP]]
;
entry:
  br label %loop

loop:
  %c = phi i32 [ %shl, %loop ], [ undef, %entry ]
  %shr = lshr i32 %c, 7
  %shl = shl i32 %shr, -2
  br label %loop
}

; Converting the 2 shifts to SHL 6 without the AND is wrong.
; https://llvm.org/bugs/show_bug.cgi?id=8547

define i32 @pr8547(ptr %g) {
; CHECK-LABEL: @pr8547(
; CHECK-NEXT:  codeRepl:
; CHECK-NEXT:    br label [[FOR_COND:%.*]]
; CHECK:       for.cond:
; CHECK-NEXT:    [[STOREMERGE:%.*]] = phi i32 [ 0, [[CODEREPL:%.*]] ], [ 5, [[FOR_COND]] ]
; CHECK-NEXT:    store i32 [[STOREMERGE]], ptr [[G:%.*]], align 4
; CHECK-NEXT:    [[TMP0:%.*]] = shl nuw nsw i32 [[STOREMERGE]], 6
; CHECK-NEXT:    [[CONV2:%.*]] = and i32 [[TMP0]], 64
; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp eq i32 [[CONV2]], 0
; CHECK-NEXT:    br i1 [[TOBOOL]], label [[FOR_COND]], label [[CODEREPL2:%.*]]
; CHECK:       codeRepl2:
; CHECK-NEXT:    ret i32 [[CONV2]]
;
codeRepl:
  br label %for.cond

for.cond:
  %storemerge = phi i32 [ 0, %codeRepl ], [ 5, %for.cond ]
  store i32 %storemerge, ptr %g, align 4
  %shl = shl i32 %storemerge, 30
  %conv2 = lshr i32 %shl, 24
  %tobool = icmp eq i32 %conv2, 0
  br i1 %tobool, label %for.cond, label %codeRepl2

codeRepl2:
  ret i32 %conv2
}

; Two same direction shifts that add up to more than the bitwidth should get
; folded to zero.

define i32 @shl_shl(i32 %A) {
; CHECK-LABEL: @shl_shl(
; CHECK-NEXT:    ret i32 0
;
  %B = shl i32 %A, 6
  %C = shl i32 %B, 28
  ret i32 %C
}

define <2 x i33> @shl_shl_splat_vec(<2 x i33> %A) {
; CHECK-LABEL: @shl_shl_splat_vec(
; CHECK-NEXT:    ret <2 x i33> zeroinitializer
;
  %B = shl <2 x i33> %A, <i33 5, i33 5>
  %C = shl <2 x i33> %B, <i33 28, i33 28>
  ret <2 x i33> %C
}

; FIXME

define <2 x i33> @shl_shl_vec(<2 x i33> %A) {
; CHECK-LABEL: @shl_shl_vec(
; CHECK-NEXT:    [[B:%.*]] = shl <2 x i33> [[A:%.*]], <i33 6, i33 5>
; CHECK-NEXT:    [[C:%.*]] = shl <2 x i33> [[B]], <i33 27, i33 28>
; CHECK-NEXT:    ret <2 x i33> [[C]]
;
  %B = shl <2 x i33> %A, <i33 6, i33 5>
  %C = shl <2 x i33> %B, <i33 27, i33 28>
  ret <2 x i33> %C
}

define i232 @lshr_lshr(i232 %A) {
; CHECK-LABEL: @lshr_lshr(
; CHECK-NEXT:    ret i232 0
;
  %B = lshr i232 %A, 231
  %C = lshr i232 %B, 1
  ret i232 %C
}

define <2 x i32> @lshr_lshr_splat_vec(<2 x i32> %A) {
; CHECK-LABEL: @lshr_lshr_splat_vec(
; CHECK-NEXT:    ret <2 x i32> zeroinitializer
;
  %B = lshr <2 x i32> %A, <i32 28, i32 28>
  %C = lshr <2 x i32> %B, <i32 4, i32 4>
  ret <2 x i32> %C
}

define <2 x i32> @lshr_lshr_vec(<2 x i32> %A) {
; CHECK-LABEL: @lshr_lshr_vec(
; CHECK-NEXT:    ret <2 x i32> zeroinitializer
;
  %B = lshr <2 x i32> %A, <i32 29, i32 28>
  %C = lshr <2 x i32> %B, <i32 4, i32 5>
  ret <2 x i32> %C
}

define i8 @shl_trunc_bigger_lshr(i32 %x) {
; CHECK-LABEL: @shl_trunc_bigger_lshr(
; CHECK-NEXT:    [[SH_DIFF:%.*]] = lshr i32 [[X:%.*]], 2
; CHECK-NEXT:    [[TR_SH_DIFF:%.*]] = trunc i32 [[SH_DIFF]] to i8
; CHECK-NEXT:    [[LT:%.*]] = and i8 [[TR_SH_DIFF]], -8
; CHECK-NEXT:    ret i8 [[LT]]
;
  %rt = lshr i32 %x, 5
  %tr = trunc i32 %rt to i8
  %lt = shl i8 %tr, 3
  ret i8 %lt
}

define i8 @shl_trunc_smaller_lshr(i32 %x) {
; CHECK-LABEL: @shl_trunc_smaller_lshr(
; CHECK-NEXT:    [[TMP1:%.*]] = trunc i32 [[X:%.*]] to i8
; CHECK-NEXT:    [[TMP2:%.*]] = shl i8 [[TMP1]], 2
; CHECK-NEXT:    [[LT:%.*]] = and i8 [[TMP2]], -32
; CHECK-NEXT:    ret i8 [[LT]]
;
  %rt = lshr i32 %x, 3
  %tr = trunc i32 %rt to i8
  %lt = shl i8 %tr, 5
  ret i8 %lt
}

define i24 @shl_trunc_bigger_ashr(i32 %x) {
; CHECK-LABEL: @shl_trunc_bigger_ashr(
; CHECK-NEXT:    [[SH_DIFF:%.*]] = ashr i32 [[X:%.*]], 9
; CHECK-NEXT:    [[TR_SH_DIFF:%.*]] = trunc i32 [[SH_DIFF]] to i24
; CHECK-NEXT:    [[LT:%.*]] = and i24 [[TR_SH_DIFF]], -8
; CHECK-NEXT:    ret i24 [[LT]]
;
  %rt = ashr i32 %x, 12
  %tr = trunc i32 %rt to i24
  %lt = shl i24 %tr, 3
  ret i24 %lt
}

define i24 @shl_trunc_smaller_ashr(i32 %x) {
; CHECK-LABEL: @shl_trunc_smaller_ashr(
; CHECK-NEXT:    [[TMP1:%.*]] = trunc i32 [[X:%.*]] to i24
; CHECK-NEXT:    [[TMP2:%.*]] = shl i24 [[TMP1]], 3
; CHECK-NEXT:    [[LT:%.*]] = and i24 [[TMP2]], -8192
; CHECK-NEXT:    ret i24 [[LT]]
;
  %rt = ashr i32 %x, 10
  %tr = trunc i32 %rt to i24
  %lt = shl i24 %tr, 13
  ret i24 %lt
}

define i8 @shl_trunc_bigger_shl(i32 %x) {
; CHECK-LABEL: @shl_trunc_bigger_shl(
; CHECK-NEXT:    [[X_TR:%.*]] = trunc i32 [[X:%.*]] to i8
; CHECK-NEXT:    [[TR:%.*]] = shl i8 [[X_TR]], 6
; CHECK-NEXT:    ret i8 [[TR]]
;
  %rt = shl i32 %x, 4
  %tr = trunc i32 %rt to i8
  %lt = shl i8 %tr, 2
  ret i8 %lt
}

define i8 @shl_trunc_smaller_shl(i32 %x) {
; CHECK-LABEL: @shl_trunc_smaller_shl(
; CHECK-NEXT:    [[X_TR:%.*]] = trunc i32 [[X:%.*]] to i8
; CHECK-NEXT:    [[TR:%.*]] = shl i8 [[X_TR]], 6
; CHECK-NEXT:    ret i8 [[TR]]
;
  %rt = shl i32 %x, 2
  %tr = trunc i32 %rt to i8
  %lt = shl i8 %tr, 4
  ret i8 %lt
}

define i8 @shl_trunc_bigger_lshr_use1(i32 %x) {
; CHECK-LABEL: @shl_trunc_bigger_lshr_use1(
; CHECK-NEXT:    [[RT:%.*]] = lshr i32 [[X:%.*]], 5
; CHECK-NEXT:    call void @use32(i32 [[RT]])
; CHECK-NEXT:    [[TR:%.*]] = trunc i32 [[RT]] to i8
; CHECK-NEXT:    [[LT:%.*]] = shl i8 [[TR]], 3
; CHECK-NEXT:    ret i8 [[LT]]
;
  %rt = lshr i32 %x, 5
  call void @use32(i32 %rt)
  %tr = trunc i32 %rt to i8
  %lt = shl i8 %tr, 3
  ret i8 %lt
}

define i8 @shl_trunc_smaller_lshr_use1(i32 %x) {
; CHECK-LABEL: @shl_trunc_smaller_lshr_use1(
; CHECK-NEXT:    [[RT:%.*]] = lshr i32 [[X:%.*]], 3
; CHECK-NEXT:    call void @use32(i32 [[RT]])
; CHECK-NEXT:    [[TR:%.*]] = trunc i32 [[RT]] to i8
; CHECK-NEXT:    [[LT:%.*]] = shl i8 [[TR]], 5
; CHECK-NEXT:    ret i8 [[LT]]
;
  %rt = lshr i32 %x, 3
  call void @use32(i32 %rt)
  %tr = trunc i32 %rt to i8
  %lt = shl i8 %tr, 5
  ret i8 %lt
}

define i8 @shl_trunc_bigger_lshr_use2(i32 %x) {
; CHECK-LABEL: @shl_trunc_bigger_lshr_use2(
; CHECK-NEXT:    [[RT:%.*]] = lshr i32 [[X:%.*]], 5
; CHECK-NEXT:    [[TR:%.*]] = trunc i32 [[RT]] to i8
; CHECK-NEXT:    call void @use8(i8 [[TR]])
; CHECK-NEXT:    [[LT:%.*]] = shl i8 [[TR]], 3
; CHECK-NEXT:    ret i8 [[LT]]
;
  %rt = lshr i32 %x, 5
  %tr = trunc i32 %rt to i8
  call void @use8(i8 %tr)
  %lt = shl i8 %tr, 3
  ret i8 %lt
}

define i8 @shl_trunc_smaller_lshr_use2(i32 %x) {
; CHECK-LABEL: @shl_trunc_smaller_lshr_use2(
; CHECK-NEXT:    [[RT:%.*]] = lshr i32 [[X:%.*]], 3
; CHECK-NEXT:    [[TR:%.*]] = trunc i32 [[RT]] to i8
; CHECK-NEXT:    call void @use8(i8 [[TR]])
; CHECK-NEXT:    [[LT:%.*]] = shl i8 [[TR]], 5
; CHECK-NEXT:    ret i8 [[LT]]
;
  %rt = lshr i32 %x, 3
  %tr = trunc i32 %rt to i8
  call void @use8(i8 %tr)
  %lt = shl i8 %tr, 5
  ret i8 %lt
}

define i32 @ashr_ashr_constants_use(i32 %x) {
; CHECK-LABEL: @ashr_ashr_constants_use(
; CHECK-NEXT:    [[S:%.*]] = ashr i32 -33, [[X:%.*]]
; CHECK-NEXT:    call void @use32(i32 [[S]])
; CHECK-NEXT:    [[R:%.*]] = ashr i32 -5, [[X]]
; CHECK-NEXT:    ret i32 [[R]]
;
  %s = ashr i32 -33, %x
  call void @use32(i32 %s)
  %r = ashr i32 %s, 3
  ret i32 %r
}

define <3 x i8> @ashr_ashr_constants_vec(<3 x i8> %x) {
; CHECK-LABEL: @ashr_ashr_constants_vec(
; CHECK-NEXT:    [[R:%.*]] = ashr <3 x i8> <i8 4, i8 poison, i8 -1>, [[X:%.*]]
; CHECK-NEXT:    ret <3 x i8> [[R]]
;
  %s = ashr <3 x i8> <i8 33, i8 -2, i8 -128>, %x
  %r = ashr <3 x i8> %s, <i8 3, i8 -1, i8 7>
  ret <3 x i8> %r
}

define i32 @lshr_lshr_constants_use(i32 %x) {
; CHECK-LABEL: @lshr_lshr_constants_use(
; CHECK-NEXT:    [[S:%.*]] = lshr i32 -33, [[X:%.*]]
; CHECK-NEXT:    call void @use32(i32 [[S]])
; CHECK-NEXT:    [[R:%.*]] = lshr i32 536870907, [[X]]
; CHECK-NEXT:    ret i32 [[R]]
;
  %s = lshr i32 -33, %x
  call void @use32(i32 %s)
  %r = lshr i32 %s, 3
  ret i32 %r
}

define <3 x i8> @lshr_lshr_constants_vec(<3 x i8> %x) {
; CHECK-LABEL: @lshr_lshr_constants_vec(
; CHECK-NEXT:    [[R:%.*]] = lshr <3 x i8> <i8 4, i8 poison, i8 0>, [[X:%.*]]
; CHECK-NEXT:    ret <3 x i8> [[R]]
;
  %s = lshr <3 x i8> <i8 33, i8 -2, i8 1>, %x
  %r = lshr <3 x i8> %s, <i8 3, i8 -1, i8 7>
  ret <3 x i8> %r
}

define i32 @shl_shl_constants_use(i32 %x) {
; CHECK-LABEL: @shl_shl_constants_use(
; CHECK-NEXT:    [[S:%.*]] = shl i32 -2013265920, [[X:%.*]]
; CHECK-NEXT:    call void @use32(i32 [[S]])
; CHECK-NEXT:    [[R:%.*]] = shl i32 1073741824, [[X]]
; CHECK-NEXT:    ret i32 [[R]]
;
  %s = shl i32 2281701376, %x ; 0x8800_0000
  call void @use32(i32 %s)
  %r = shl i32 %s, 3
  ret i32 %r
}

define <3 x i8> @shl_shl_constants_vec(<3 x i8> %x) {
; CHECK-LABEL: @shl_shl_constants_vec(
; CHECK-NEXT:    [[R:%.*]] = shl <3 x i8> <i8 8, i8 poison, i8 0>, [[X:%.*]]
; CHECK-NEXT:    ret <3 x i8> [[R]]
;
  %s = shl <3 x i8> <i8 33, i8 -2, i8 -128>, %x
  %r = shl <3 x i8> %s, <i8 3, i8 -1, i8 7>
  ret <3 x i8> %r
}

; PR9809
define i32 @shl_shl_constants_div(i32 %a, i32 %b) {
; CHECK-LABEL: @shl_shl_constants_div(
; CHECK-NEXT:    [[TMP1:%.*]] = add i32 [[B:%.*]], 2
; CHECK-NEXT:    [[DIV1:%.*]] = lshr i32 [[A:%.*]], [[TMP1]]
; CHECK-NEXT:    ret i32 [[DIV1]]
;
  %shl1 = shl i32 1, %b
  %shl2 = shl i32 %shl1, 2
  %div = udiv i32 %a, %shl2
  ret i32 %div
}

define i32 @ashr_lshr_constants(i32 %x) {
; CHECK-LABEL: @ashr_lshr_constants(
; CHECK-NEXT:    [[S:%.*]] = ashr i32 -33, [[X:%.*]]
; CHECK-NEXT:    [[R:%.*]] = lshr i32 [[S]], 3
; CHECK-NEXT:    ret i32 [[R]]
;
  %s = ashr i32 -33, %x
  %r = lshr i32 %s, 3
  ret i32 %r
}

define i32 @ashr_shl_constants(i32 %x) {
; CHECK-LABEL: @ashr_shl_constants(
; CHECK-NEXT:    [[S:%.*]] = ashr i32 -33, [[X:%.*]]
; CHECK-NEXT:    [[R:%.*]] = shl nsw i32 [[S]], 3
; CHECK-NEXT:    ret i32 [[R]]
;
  %s = ashr i32 -33, %x
  %r = shl i32 %s, 3
  ret i32 %r
}

define i32 @lshr_ashr_constants(i32 %x) {
; CHECK-LABEL: @lshr_ashr_constants(
; CHECK-NEXT:    [[S:%.*]] = lshr i32 -33, [[X:%.*]]
; CHECK-NEXT:    [[R:%.*]] = ashr i32 [[S]], 3
; CHECK-NEXT:    ret i32 [[R]]
;
  %s = lshr i32 -33, %x
  %r = ashr i32 %s, 3
  ret i32 %r
}

define i32 @lshr_shl_constants(i32 %x) {
; CHECK-LABEL: @lshr_shl_constants(
; CHECK-NEXT:    [[S:%.*]] = lshr i32 -33, [[X:%.*]]
; CHECK-NEXT:    [[R:%.*]] = shl i32 [[S]], 3
; CHECK-NEXT:    ret i32 [[R]]
;
  %s = lshr i32 -33, %x
  %r = shl i32 %s, 3
  ret i32 %r
}

define i32 @shl_ashr_constants(i32 %x) {
; CHECK-LABEL: @shl_ashr_constants(
; CHECK-NEXT:    [[S:%.*]] = shl i32 -33, [[X:%.*]]
; CHECK-NEXT:    [[R:%.*]] = ashr i32 [[S]], 3
; CHECK-NEXT:    ret i32 [[R]]
;
  %s = shl i32 -33, %x
  %r = ashr i32 %s, 3
  ret i32 %r
}

define i32 @shl_lshr_constants(i32 %x) {
; CHECK-LABEL: @shl_lshr_constants(
; CHECK-NEXT:    [[S:%.*]] = shl i32 -33, [[X:%.*]]
; CHECK-NEXT:    [[R:%.*]] = lshr i32 [[S]], 3
; CHECK-NEXT:    ret i32 [[R]]
;
  %s = shl i32 -33, %x
  %r = lshr i32 %s, 3
  ret i32 %r
}

; Pre-shift a constant to eliminate lshr.

define i8 @shl_lshr_demand1(i8 %x) {
; CHECK-LABEL: @shl_lshr_demand1(
; CHECK-NEXT:    [[TMP1:%.*]] = shl i8 5, [[X:%.*]]
; CHECK-NEXT:    [[R:%.*]] = or i8 [[TMP1]], -32
; CHECK-NEXT:    ret i8 [[R]]
;
  %shl = shl i8 40, %x ; 0b0010_1000
  %lshr = lshr i8 %shl, 3
  %r = or i8 %lshr, 224 ; 0b1110_0000
  ret i8 %r
}

; Pre-shift a constant to eliminate disguised lshr.

define i8 @shl_ashr_demand2(i8 %x) {
; CHECK-LABEL: @shl_ashr_demand2(
; CHECK-NEXT:    [[SHL:%.*]] = shl i8 40, [[X:%.*]]
; CHECK-NEXT:    call void @use8(i8 [[SHL]])
; CHECK-NEXT:    [[TMP1:%.*]] = shl i8 5, [[X]]
; CHECK-NEXT:    [[R:%.*]] = or i8 [[TMP1]], -32
; CHECK-NEXT:    ret i8 [[R]]
;
  %shl = shl i8 40, %x ; 0b0010_1000
  call void @use8(i8 %shl)
  %lshr = ashr i8 %shl, 3
  %r = or i8 %lshr, 224 ; 0b1110_0000
  ret i8 %r
}

; It is not safe to pre-shift because we demand an extra high bit.

define i8 @shl_lshr_demand3(i8 %x) {
; CHECK-LABEL: @shl_lshr_demand3(
; CHECK-NEXT:    [[SHL:%.*]] = shl i8 40, [[X:%.*]]
; CHECK-NEXT:    [[LSHR:%.*]] = lshr exact i8 [[SHL]], 3
; CHECK-NEXT:    [[R:%.*]] = or i8 [[LSHR]], -64
; CHECK-NEXT:    ret i8 [[R]]
;
  %shl = shl i8 40, %x ; 0b0010_1000
  %lshr = lshr i8 %shl, 3
  %r = or i8 %lshr, 192 ; 0b1100_0000
  ret i8 %r
}

; It is not valid to pre-shift because we lose the low bit of 44.

define i8 @shl_lshr_demand4(i8 %x) {
; CHECK-LABEL: @shl_lshr_demand4(
; CHECK-NEXT:    [[SHL:%.*]] = shl i8 44, [[X:%.*]]
; CHECK-NEXT:    [[LSHR:%.*]] = lshr i8 [[SHL]], 3
; CHECK-NEXT:    [[R:%.*]] = or i8 [[LSHR]], -32
; CHECK-NEXT:    ret i8 [[R]]
;
  %shl = shl i8 44, %x ; 0b0010_1100
  %lshr = lshr i8 %shl, 3
  %r = or i8 %lshr, 224 ; 0b1110_0000
  ret i8 %r
}

; Splat vectors work too, and we don't care what instruction reduces demand for high bits.

define <2 x i6> @shl_lshr_demand5(<2 x i8> %x) {
; CHECK-LABEL: @shl_lshr_demand5(
; CHECK-NEXT:    [[TMP1:%.*]] = shl <2 x i8> <i8 37, i8 37>, [[X:%.*]]
; CHECK-NEXT:    [[R:%.*]] = trunc <2 x i8> [[TMP1]] to <2 x i6>
; CHECK-NEXT:    ret <2 x i6> [[R]]
;
  %shl = shl <2 x i8> <i8 148, i8 148>, %x ; 0b1001_0100
  %lshr = lshr <2 x i8> %shl, <i8 2, i8 2>
  %r = trunc <2 x i8> %lshr to <2 x i6>
  ret <2 x i6> %r
}

; TODO: allow undef/poison elements for this transform.

define <2 x i6> @shl_lshr_demand5_undef_left(<2 x i8> %x) {
; CHECK-LABEL: @shl_lshr_demand5_undef_left(
; CHECK-NEXT:    [[SHL:%.*]] = shl <2 x i8> <i8 undef, i8 -108>, [[X:%.*]]
; CHECK-NEXT:    [[LSHR:%.*]] = lshr <2 x i8> [[SHL]], <i8 2, i8 2>
; CHECK-NEXT:    [[R:%.*]] = trunc <2 x i8> [[LSHR]] to <2 x i6>
; CHECK-NEXT:    ret <2 x i6> [[R]]
;
  %shl = shl <2 x i8> <i8 undef, i8 148>, %x ; 0b1001_0100
  %lshr = lshr <2 x i8> %shl, <i8 2, i8 2>
  %r = trunc <2 x i8> %lshr to <2 x i6>
  ret <2 x i6> %r
}

; TODO: allow undef/poison elements for this transform.

define <2 x i6> @shl_lshr_demand5_undef_right(<2 x i8> %x) {
; CHECK-LABEL: @shl_lshr_demand5_undef_right(
; CHECK-NEXT:    [[SHL:%.*]] = shl <2 x i8> <i8 -108, i8 -108>, [[X:%.*]]
; CHECK-NEXT:    [[LSHR:%.*]] = lshr <2 x i8> [[SHL]], <i8 undef, i8 2>
; CHECK-NEXT:    [[R:%.*]] = trunc <2 x i8> [[LSHR]] to <2 x i6>
; CHECK-NEXT:    ret <2 x i6> [[R]]
;
  %shl = shl <2 x i8> <i8 148, i8 148>, %x ; 0b1001_0100
  %lshr = lshr <2 x i8> %shl, <i8 undef, i8 2>
  %r = trunc <2 x i8> %lshr to <2 x i6>
  ret <2 x i6> %r
}

; TODO: allow non-splat vector constants.

define <2 x i6> @shl_lshr_demand5_nonuniform_vec_left(<2 x i8> %x) {
; CHECK-LABEL: @shl_lshr_demand5_nonuniform_vec_left(
; CHECK-NEXT:    [[SHL:%.*]] = shl <2 x i8> <i8 -108, i8 -108>, [[X:%.*]]
; CHECK-NEXT:    [[LSHR:%.*]] = lshr <2 x i8> [[SHL]], <i8 1, i8 2>
; CHECK-NEXT:    [[R:%.*]] = trunc <2 x i8> [[LSHR]] to <2 x i6>
; CHECK-NEXT:    ret <2 x i6> [[R]]
;
  %shl = shl <2 x i8> <i8 148, i8 148>, %x ; 0b1001_0100
  %lshr = lshr <2 x i8> %shl, <i8 1, i8 2>
  %r = trunc <2 x i8> %lshr to <2 x i6>
  ret <2 x i6> %r
}

; non-splat shl constant is ok.

define <2 x i6> @shl_lshr_demand5_nonuniform_vec_right(<2 x i8> %x) {
; CHECK-LABEL: @shl_lshr_demand5_nonuniform_vec_right(
; CHECK-NEXT:    [[TMP1:%.*]] = shl <2 x i8> <i8 37, i8 36>, [[X:%.*]]
; CHECK-NEXT:    [[R:%.*]] = trunc <2 x i8> [[TMP1]] to <2 x i6>
; CHECK-NEXT:    ret <2 x i6> [[R]]
;
  %shl = shl <2 x i8> <i8 148, i8 144>, %x ; 0b1001_0100, 0b1001_0000
  %lshr = lshr <2 x i8> %shl, <i8 2, i8 2>
  %r = trunc <2 x i8> %lshr to <2 x i6>
  ret <2 x i6> %r
}

; This is possible, but may require significant changes to the demanded bits framework.

define <2 x i6> @shl_lshr_demand5_nonuniform_vec_both(<2 x i8> %x) {
; CHECK-LABEL: @shl_lshr_demand5_nonuniform_vec_both(
; CHECK-NEXT:    [[SHL:%.*]] = shl <2 x i8> <i8 -104, i8 -108>, [[X:%.*]]
; CHECK-NEXT:    [[LSHR:%.*]] = lshr <2 x i8> [[SHL]], <i8 3, i8 2>
; CHECK-NEXT:    [[R:%.*]] = trunc <2 x i8> [[LSHR]] to <2 x i6>
; CHECK-NEXT:    ret <2 x i6> [[R]]
;
  %shl = shl <2 x i8> <i8 152, i8 148>, %x ; 0b1001_1000, 0b1001_0100
  %lshr = lshr <2 x i8> %shl, <i8 3, i8 2>
  %r = trunc <2 x i8> %lshr to <2 x i6>
  ret <2 x i6> %r
}

; 'and' can reduce demand for high bits too.

define i16 @shl_lshr_demand6(i16 %x) {
; CHECK-LABEL: @shl_lshr_demand6(
; CHECK-NEXT:    [[TMP1:%.*]] = shl i16 2057, [[X:%.*]]
; CHECK-NEXT:    [[R:%.*]] = and i16 [[TMP1]], 4094
; CHECK-NEXT:    ret i16 [[R]]
;
  %shl = shl i16 32912, %x ; 0b1000_0000_1001_0000
  %lshr = lshr i16 %shl, 4
  %r = and i16 %lshr, 4094 ; 0b0000_1111_1111_1110
  ret i16 %r
}

; Pre-shift a constant to eliminate shl.

define i8 @lshr_shl_demand1(i8 %x) {
; CHECK-LABEL: @lshr_shl_demand1(
; CHECK-NEXT:    [[TMP1:%.*]] = lshr i8 -32, [[X:%.*]]
; CHECK-NEXT:    [[R:%.*]] = or i8 [[TMP1]], 7
; CHECK-NEXT:    ret i8 [[R]]
;
  %shr = lshr i8 28, %x ; 0b0001_1100
  %shl = shl i8 %shr, 3
  %r = or i8 %shl, 7    ; 0b0000_0111
  ret i8 %r
}

; Extra use on lshr is ok and 'and' is another demand limiter.

define i8 @lshr_shl_demand2(i8 %x) {
; CHECK-LABEL: @lshr_shl_demand2(
; CHECK-NEXT:    [[SHR:%.*]] = lshr i8 28, [[X:%.*]]
; CHECK-NEXT:    call void @use8(i8 [[SHR]])
; CHECK-NEXT:    [[TMP1:%.*]] = lshr i8 -32, [[X]]
; CHECK-NEXT:    [[R:%.*]] = and i8 [[TMP1]], -16
; CHECK-NEXT:    ret i8 [[R]]
;
  %shr = lshr i8 28, %x ; 0b0001_1100
  call void @use8(i8 %shr)
  %shl = shl i8 %shr, 3
  %r = and i8 %shl, -16 ; 0b1111_0000
  ret i8 %r
}

; It is not safe to pre-shift because we demand an extra low bit.

define i8 @lshr_shl_demand3(i8 %x) {
; CHECK-LABEL: @lshr_shl_demand3(
; CHECK-NEXT:    [[SHR:%.*]] = lshr i8 28, [[X:%.*]]
; CHECK-NEXT:    [[SHL:%.*]] = shl nuw i8 [[SHR]], 3
; CHECK-NEXT:    [[R:%.*]] = or i8 [[SHL]], 3
; CHECK-NEXT:    ret i8 [[R]]
;
  %shr = lshr i8 28, %x ; 0b0001_1100
  %shl = shl i8 %shr, 3
  %r = or i8 %shl, 3    ; 0b0000_0011
  ret i8 %r
}

; It is not valid to pre-shift because we lose the high bit of 60.

define i8 @lshr_shl_demand4(i8 %x) {
; CHECK-LABEL: @lshr_shl_demand4(
; CHECK-NEXT:    [[SHR:%.*]] = lshr i8 60, [[X:%.*]]
; CHECK-NEXT:    [[SHL:%.*]] = shl i8 [[SHR]], 3
; CHECK-NEXT:    [[R:%.*]] = or i8 [[SHL]], 7
; CHECK-NEXT:    ret i8 [[R]]
;
  %shr = lshr i8 60, %x ; 0b0011_1100
  %shl = shl i8 %shr, 3
  %r = or i8 %shl, 7    ; 0b0000_0111
  ret i8 %r
}

; Splat vectors work too.

define <2 x i8> @lshr_shl_demand5(<2 x i8> %x) {
; CHECK-LABEL: @lshr_shl_demand5(
; CHECK-NEXT:    [[TMP1:%.*]] = lshr <2 x i8> <i8 -76, i8 -76>, [[X:%.*]]
; CHECK-NEXT:    [[R:%.*]] = and <2 x i8> [[TMP1]], <i8 108, i8 108>
; CHECK-NEXT:    ret <2 x i8> [[R]]
;
  %shr = lshr <2 x i8> <i8 45, i8 45>, %x ; 0b0010_1101
  %shl = shl <2 x i8> %shr, <i8 2, i8 2>
  %r = and <2 x i8> %shl, <i8 108, i8 108> ; 0b0110_1100
  ret <2 x i8> %r
}

; TODO: allow undef/poison elements for this transform.

define <2 x i8> @lshr_shl_demand5_undef_left(<2 x i8> %x) {
; CHECK-LABEL: @lshr_shl_demand5_undef_left(
; CHECK-NEXT:    [[SHR:%.*]] = lshr <2 x i8> <i8 45, i8 45>, [[X:%.*]]
; CHECK-NEXT:    [[SHL:%.*]] = shl <2 x i8> [[SHR]], <i8 undef, i8 2>
; CHECK-NEXT:    [[R:%.*]] = and <2 x i8> [[SHL]], <i8 108, i8 108>
; CHECK-NEXT:    ret <2 x i8> [[R]]
;
  %shr = lshr <2 x i8> <i8 45, i8 45>, %x ; 0b0010_1101
  %shl = shl <2 x i8> %shr, <i8 undef, i8 2>
  %r = and <2 x i8> %shl, <i8 108, i8 108> ; 0b0110_1100
  ret <2 x i8> %r
}

; TODO: allow undef/poison elements for this transform.

define <2 x i8> @lshr_shl_demand5_undef_right(<2 x i8> %x) {
; CHECK-LABEL: @lshr_shl_demand5_undef_right(
; CHECK-NEXT:    [[SHR:%.*]] = lshr <2 x i8> <i8 undef, i8 45>, [[X:%.*]]
; CHECK-NEXT:    [[SHL:%.*]] = shl <2 x i8> [[SHR]], <i8 2, i8 2>
; CHECK-NEXT:    [[R:%.*]] = and <2 x i8> [[SHL]], <i8 108, i8 108>
; CHECK-NEXT:    ret <2 x i8> [[R]]
;
  %shr = lshr <2 x i8> <i8 undef, i8 45>, %x ; 0b0010_1101
  %shl = shl <2 x i8> %shr, <i8 2, i8 2>
  %r = and <2 x i8> %shl, <i8 108, i8 108> ; 0b0110_1100
  ret <2 x i8> %r
}

; TODO: allow non-splat vector constants.

define <2 x i8> @lshr_shl_demand5_nonuniform_vec_left(<2 x i8> %x) {
; CHECK-LABEL: @lshr_shl_demand5_nonuniform_vec_left(
; CHECK-NEXT:    [[SHR:%.*]] = lshr <2 x i8> <i8 45, i8 45>, [[X:%.*]]
; CHECK-NEXT:    [[SHL:%.*]] = shl <2 x i8> [[SHR]], <i8 1, i8 2>
; CHECK-NEXT:    [[R:%.*]] = and <2 x i8> [[SHL]], <i8 108, i8 108>
; CHECK-NEXT:    ret <2 x i8> [[R]]
;
  %shr = lshr <2 x i8> <i8 45, i8 45>, %x ; 0b0010_1101
  %shl = shl <2 x i8> %shr, <i8 1, i8 2>
  %r = and <2 x i8> %shl, <i8 108, i8 108> ; 0b0110_1100
  ret <2 x i8> %r
}

; non-splat lshr constant is ok.

define <2 x i8> @lshr_shl_demand5_nonuniform_vec_right(<2 x i8> %x) {
; CHECK-LABEL: @lshr_shl_demand5_nonuniform_vec_right(
; CHECK-NEXT:    [[TMP1:%.*]] = lshr <2 x i8> <i8 -76, i8 52>, [[X:%.*]]
; CHECK-NEXT:    [[R:%.*]] = and <2 x i8> [[TMP1]], <i8 108, i8 108>
; CHECK-NEXT:    ret <2 x i8> [[R]]
;
  %shr = lshr <2 x i8> <i8 45, i8 13>, %x ; 0b0010_1101. 0b0000_1101
  %shl = shl <2 x i8> %shr, <i8 2, i8 2>
  %r = and <2 x i8> %shl, <i8 108, i8 108> ; 0b0110_1100
  ret <2 x i8> %r
}

; This is possible, but may require significant changes to the demanded bits framework.

define <2 x i8> @lshr_shl_demand5_nonuniform_vec_both(<2 x i8> %x) {
; CHECK-LABEL: @lshr_shl_demand5_nonuniform_vec_both(
; CHECK-NEXT:    [[SHR:%.*]] = lshr <2 x i8> <i8 45, i8 13>, [[X:%.*]]
; CHECK-NEXT:    [[SHL:%.*]] = shl <2 x i8> [[SHR]], <i8 2, i8 4>
; CHECK-NEXT:    [[R:%.*]] = and <2 x i8> [[SHL]], <i8 -4, i8 -16>
; CHECK-NEXT:    ret <2 x i8> [[R]]
;
  %shr = lshr <2 x i8> <i8 45, i8 13>, %x ; 0b0010_1101. 0b0000_1101
  %shl = shl <2 x i8> %shr, <i8 2, i8 4>
  %r = and <2 x i8> %shl, <i8 -4, i8 -16>
  ret <2 x i8> %r
}
